package shujujiegou;

import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class zhongxubianli {
   static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    public static List<Integer> list=new ArrayList<>();
    public static List<Integer> inorderTraversal(TreeNode root) {
        if(root==null){
            return list;
        }
        Stack<TreeNode> Stack=new Stack<>();
        TreeNode cur=root;
        while(!Stack.isEmpty()||cur!=null){
            while(cur!=null){
                Stack.push(cur);
                cur=cur.left;
            }
            cur=Stack.pop();
            list.add(cur.val);
            cur=cur.right;
        }
        return list;

    }

    public static void main(String[] args) {
        TreeNode a=new TreeNode(1);
        TreeNode b=new TreeNode(2);
        TreeNode c=new TreeNode(3);
        TreeNode d=new TreeNode(4);
        TreeNode e=new TreeNode(5);
        TreeNode f=new TreeNode(8);
        TreeNode g=new TreeNode(6);
        TreeNode h=new TreeNode(7);
        TreeNode m=new TreeNode(9);
        a.left=b;
        a.right=c;
        b.left=d;
        b.right=e;
        e.left=g;
        e.right=h;
        c.right=f;
        f.left=m;
        List<Integer> list1 = inorderTraversal(a);
        System.out.println(list1);


    }
}
